15. Video: Is that the Optimal Solution?

A Couple Other Points

In this video, you saw that how the starting points of the centroids can actually make a difference as to the final results you obtain from the k-means algorithm.

In order to assure you have the "best" set of clusters, the algorithm you saw earlier will be performed a few times with different starting points. The best set of clusters is then the clustering that creates the smallest average distance from each point to its corresponding centroid.